Large sets are sumsets

Abstract: Let $[n] :=\{0,1,2,\dots,n\}$. Intuitively, all large subsets of $[n]$ have additive structure, and Roth famously made this precise by finding constants $c$, $N > 0$ such that for $n \geq N$, any subset of $[n]$ containing more than $\frac{cn}{\log\log n}$ elements must contain an arithmetic progression of length $3$. We establish a different interpretation of the intuition by finding explicit constants $\alpha = \frac{1}{\log 2}$ and $\beta = \frac{1}{\log 1.325}$ such that, for sufficiently large $n$, we have: \begin{enumerate} \item[(i)] any subset of $[n]$ with more than $n-\alpha \log n$ elements has a nontrivial decomposition as the sum of two sets, and

\item [(ii)]there exists a subset of $[n]$ of size $n - \beta \log n$ at least that has no such decomposition.

\end{enumerate} We also prove, using these methods, a higher-dimensional analogue of results (i) and (ii). Notably, our threshold at which structure appears is far higher than Roth's.

This work was joint with Justine Dell, Sophia Dever, Adam Dionne, Faye Jackson, Leo Goldmakher, Gal Gross, Steven J. Miller, Ethan Pesikoff, Huy Tuan Pham, Luke Reifenberg, and Vidya Venkatesh. \\

number theory

Audience: researchers in the discipline

Combinatorial and additive number theory (CANT 2022)